package likou.offer;

/**
 * @Info:
 * @Author: 唐小尊
 * @Date: 2020/8/16  13:11
 */
public class _33 {
    public static void main(String[] args) {
        int ss[] = {5, 2, -17, -11, 25, 76, 62, 98, 92, 61};
        System.out.println(verifyPostorder(ss));
    }

    public static boolean verifyPostorder(int[] postorder) {
        return yanzheng(postorder, 0, postorder.length - 1, postorder[postorder.length - 1]);
    }

    public static boolean yanzheng(int[] postorder, int low, int high, int max) {
        if (high - low <= 1) {
            return true;
        }
        //System.out.println(low + ":" + postorder[low] + "   " + high + ":" + postorder[high] + "   " + max);
        for (int i = low; i < high; i++) {
            if (postorder[i] > max) {
                int pp = i + 1;
                //判断右数中是否有比自己小的
                while (pp < high) {
                    if (postorder[pp] < max) {
                        return false;
                    }
                    pp++;
                }

                boolean left = true;
                boolean right = true;
                if (i >= 1) {
                    left = yanzheng(postorder, low, i - 1, postorder[i - 1]);
                }
                if (i <= high - 1) {
                    right = yanzheng(postorder, i, high - 1, postorder[high - 1]);
                }
                return left && right;
            }
        }
        //没找到比当前最后更大的，说明当前这个为最右下角的。
        return yanzheng(postorder, low, high - 1, postorder[high - 1]);
    }
}
